package com.atguigu.distributed.lock.leecode.tree;

import com.atguigu.distributed.lock.leecode.TreeNode;

/**
 * 力扣困难124：二叉树中的最大路径和
 */
public class MaxPathSum {
    int maxPath = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxPath;
    }

    public int maxGain(TreeNode node) {
        if (node == null){
            return 0;
        }
        //递归计算左右子节点的最大贡献值
        //只有在最大贡献值大于0时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left),0);
        int rightGain = Math.max(maxGain(node.right),0);
        //节点的最大路径和取决于该节点的值和该节点的左右子节点的最大贡献值
        int priceNewpath = node.data + leftGain +rightGain;

        //更新答案
        maxPath = Math.max(maxPath,priceNewpath);
        //返回节点的最大贡献值
        return node.data + Math.max(leftGain,rightGain);
    }

}
